#ifndef DATALIST_H
#define DATALIST_H
#include<iostream>
#include<time.h>
#include<stdlib.h>
#include<stdio.h>
const int DefaultSize = 100;
using namespace std;

template<class T>
class Element{
	public:
		Element<T> &   operator=(const Element<T>& x){
			key=x.key;
			return *this;
		}
		int setKey(const T & x){
			key = x;
			return 0;
		}
		bool operator== (Element<T>& x){
			return key == x.key;
		}
		bool operator<=(Element<T>& x){
			return key <=x.key;
		}
		bool operator>=(Element<T>& x){
			return key >= x.key;
		}
		bool operator!=(Element<T>& x){
			return key != x.key;
		}
		bool operator<(Element<T>& x){
			return key <x.key;
		}
		bool operator>(Element<T>& x){
			return key > x.key;
		}
		friend ostream& operator<<(ostream &os,Element<T> &x){
			cout<<x.key;
			return os ;
		}
		T key;
};

template<class T>
class dataList{
	public:
		dataList(int maxSz = DefaultSize):maxSize(maxSz),currentSize(0){
			vec = new Element<T>[maxSz];
		}

	public:
		void insert(const Element<T> &x){
			vec[currentSize ] = x;
			currentSize ++;
		}
		void  Swap(Element<T>& x,Element<T>& y){
			Element<T> temp;
			temp.key = x.key;
			x.key = y.key;
			y.key = temp.key;
		}
		void PrintDataList(){
			for(int i= 0;i<currentSize;i++)
				cout<<vec[i]<<" ";
			cout<<endl;
		}
		int Length(){ return currentSize;}
		Element<T>& operator[](int i){
			return vec[i];
		
		}
		int Partition(const int low,const int high){
			Element<int> temp  = vec[high];
			int i = low -1;
			for(int j=low ;j<high;j++){
				if(vec[j] < temp){
					i  = i+1;
					if(vec[i] != vec[j])
						Swap(vec[i],vec[j]);
				}
			}
			Swap(vec[i+1],vec[high]);
			return i+1;

		}
	private:
		Element<T> * vec;
		int maxSize;
		int currentSize;
};


template<class T>
void BubbleSort(dataList<T>& L,const int left,const int right){
	bool exchanged;
	for(int i=right;i>left;i--){
		exchanged = false;
		for(int j= i-1;j>=left;j--){
			if(L[i] < L[j]){
				L.Swap(L[i],L[j]);
				exchanged = true;
			}
		}
		if(exchanged == false)
			break;
	}
	L.PrintDataList();
}

template<class T>
void InsertSort(dataList<T>& L,const int left,const int right){
	Element<T> temp;
	int j = left;
	for(int i = left+1;i<=right;i++){
		if(L[i] < L[i-1]){
			temp = L[i];
			j= i-1;
		}
		do{
			L[j+1] = L[j];
			j--;
		}while(j>=left && L[j] > temp);
		L[j+1] = temp;
	}

	L.PrintDataList();
}
template<class T>
void ShellSort(dataList<T>&L,const int left,const int right){
	int gap = right -left +1;
	int j;
	Element<T> temp;
	do{
		gap = gap/3 +1;
		for(int i=left + gap;i<=right;i +=gap){
			if(L[i] < L[i-gap]){
				temp = L[i];
				j= i-gap;
				do{
					L[j+gap] = L[j];
					j -=gap;
				}while(j>=left && L[j] > temp);
				L[j+gap] = temp;
			}
		}
	}while(gap> 1);
	L.PrintDataList();
}
template<class T>
void QSort(dataList<T> &L,const int left,const int right){
	int pivot;
	if(left < right){
		pivot = L.Partition(left,right);
		QSort(L,left,pivot-1);
		QSort(L,pivot +1,right);
	}
}
template<class T>
void QuickSort(dataList<T>& L,const int left,const int right){
	L.PrintDataList();
	srandom(time(NULL));
	double temp = (right -left)*(random()*1.0 / RAND_MAX);
	int pivot = left + (int)temp;
	L.Swap(L[right],L[pivot]);
	L.PrintDataList();
	QSort(L,left,right);
	L.PrintDataList();

}
template<class T>
void SelectSort(dataList<T>& L,const int left,const int right){
	Element<int> min;
	int minIndex;
	for(int i=left;i<right;i++){
		min = L[i];
		minIndex = i;
		for(int j= i+1;j<= right;j++){
			if(L[j] < min){
				min = L[j];
				minIndex = j;
			}
		}
		if(min != L[i]){
			L.Swap(L[i],L[minIndex]);
		}
	}
	L.PrintDataList();
}


template<class T>
void merge(dataList<T> &L,int start,int mid,int end){
	dataList<T> lTemp(L.Length());	
	int i=start;
	int j = mid +1;
	while(i<=mid || j<= end){
		if(L[i] < L[j]){
			lTemp.insert(L[i++]);
		}else
			lTemp.insert(L[j++]);
	}
	while(i<=mid){
		lTemp.insert(L[i++]);
	}
	while(j<=end){
		lTemp.insert(L[j++]);
	}
	for(int i=start;i<=end;i++){
		L[i] = lTemp[i];
	}
}
template<class T>
void MergeSort(dataList<T>&L,int start ,int end){
	if(start >= end)
		return;
	int mid = (start + end/2);
	MergeSort(L,start,mid);
	MergeSort(L,mid+1,end);
	merge(L,start,mid,end);
	L.PrintDataList();
}

template<class T>
void siftDown(dataList<T> &L ,int start,int end){
	Element<int> lTemp = L[start];
	int i=start;
	int j=2 * i +1;
	while(j <= end){
		if(j +1 <= end && L[j] < L[j+1])
			j= j+1;
		if(L[j] >lTemp){
			L[i] = L[j];
			i=j;
			j = 2*i +1;
		}else
			break;
	}
	L[i] = lTemp;
}

template<class T>
void HeapSort(dataList<T> & L){
	int currentSize = L.Length();
	for(int i= (currentSize-2)/2;i>=0;i--){
		siftDown(L,i,currentSize -1);
	}
	for(int i=currentSize-1;i>0;i--){
		L.Swap(L[0],L[i]);
		siftDown(L,0,i-1);
	}
	L.PrintDataList();
}


#endif
